本文转载时请标注出处 − 不讲魔法讲道理 C S D N \color{red}{本文转载时请标注出处-不讲魔法讲道理CSDN} 本文转载时请标注出处−不讲魔法讲道理CSDN

前言：对于以下两个IETF标准 （一）2007 RFC 5053: Raptor forward error correction scheme: Scheme for object delivery （二）2011 RaptorQ Forward Error Correction Scheme for Object Delivery, document RFC 6330   基本所有的Raptor码相关论文都会引用的两个标准，然而目前网上没有比较系统的中文整理。本文对文献（一）进行系统学习及整理，以方便后来人更快入门。

M. Luby, A. Shokrollahi, M. Watson, and T. Stockhammer, “RFC 5053: Raptor forward error correction scheme: Scheme for object delivery,” IETF, Tech. Rep., Oct. 2007.旨在为Raptor前向纠错码及其在数据对象的可靠交付中的应用提供参考。注意该标准是建立在GF(2)上，而6330是RaptorQ。

后续见Raptor（二）：2011 RFC6330标准学习

  作为喷泉码，编码器可以根据需要从一个数据源块的源符号中即时生成任意数量的编码符号。 解码器能够从任何一组只比源符号数量稍多的编码符号中恢复源块。   本标准构建了系统化Raptor码，使得所有的源符号都包含在生成的编码符号之中。

  FEC有效载荷ID定义为一个32位段，Source Block Number (SBN)占16bit，Encoding Symbol ID (ESI)占16bit，前者指示数据包内编码符号所涉及的源块标志；后者指示数据包内编码符号的标识。

  也就是说该标准中Raptor码需要加载32位的负载，前16位用于告知该编码符号来自于哪一个源数据块，后16位用于告知该编码符号是该源数据块的第几个编码符号。

  后续会在Sec 5 中进一步定义如何编号。

  前者是一个不超过 2 45 2^{45} 245的非负整数，用45bit表示；后者是一个不超过 2 16 2^{16} 216的非负整数，用16bit表示。

  对符号大小限制为2^16-1限制了传输长度小于 2 45 2^{45} 245。对一个源块中的符号数量的限制为 2 13 2^{13} 213。对源块数量的限制为 2 16 2^{16} 216。   实际操作中，为了简单起见，传输长度被编码为一个48位的字段。

Scheme-Specific OTI（4字节）：

该FEC方案的特定FEC对象传输信息元素中包含：

总结：编码后FEC对象传输信息是一个14字节（14*8bit）的字段。

  后续在Sec 5.3.1.2 中进一步定义每个段的二进制流如何生成。

  描述Raptor FEC方案与对象传送的内容传送协议（CDP）之间的信息交换，用于对象传送的Raptor编码器和解码器需要CDP提供以下信息：

此外Raptor编码器还需要（非CDP提供）

Raptor编码器为每个要发送的数据包向CDP提供以下信息：

  针对4.1中的参数，给出传输参数T、Z和N的推导提供建议，该建议是基于以下输入参数：

注意，对于一个给定的W值，实际的最大解码器内存需求取决于实现，但有可能使用仅略大于W的工作内存实现解码。

输出：

G = min{ceil(P*Kmin/F), P/Al, Gmax} 代表在一个数据包中传输的最大符号数。

T = floor(P/(Al*G))*Al ，The symbol size

注意以上G、T是下限估计，实际中往往会增加到最接近的2的幂。在数据包最大有效载荷P/符号对齐参数AI=G的情况中，P/T是一个整数。

Kt = ceil(F/T)，表示对象的源数据所需的符号总数。

Z = ceil(Kt/Kmax)，The number of source blocks

N = min{ceil(ceil(Kt/Z)*T/W), T/Al}，The number of sub-blocks

  该参数推导算法确保子符号的大小是符号对齐参数Al的倍数。 用于编码和解码的XOR操作通常是一次执行几个字节，例如，在32位处理器上一次至少执行4个字节。 因此，如果子符号大小是这个字节数的倍数，那么编码和解码的执行速度就会更快。

一般来说置AI=4 bytes，Kmin = 1024 bytes，Gmax=10。

信源→信源编码→信道编码→数字调制→信道，源符号是指经过信道编码后的符号流。

  系统化Raptor码的主要组成部分是第5.4节中描述的基本编码器: 首先描述如何从原始源符号中得出一组中间符号的值，从而使对中间符号的了解足以重建源符号。 其次，编码器产生修复符号，它们都是一些中间符号的异或。 编码符号是源符号和修复符号的组合。 修复符号是以中间符号产生的，因此也是源符号，可以从任何足够大的编码符号集中恢复。   5.5提供了一种有效的解码算法。实际上系统化的Raptor码编码有许多可能的解码算法。   5.6提供用于中间符号和修复符号的构造的伪随机数。伪随机数发生器基于一组固定的512个随机数，这些随机数发送方和接收方都可用。   从源符号中构建中间符号受 "系统指数J（K） "的制约，5.7中提供了J（K）的值，以便在从4个源符号到Kmax=8192个源符号变动时确定源块的大小。

  为将Raptor编码器应用于源对象，该对象可以被分解成Z >= 1个源块。编码独立作用于源块，每个源块用SBN标识，标识数从0到Z-1。每个源块划分成K个源符号，每个符号大小为T字节，每个源符号用ESI标识，标识数从0到K-1。   每个包含K个源符号的源块可被划分为N个子块，子块足够小，可以在工作储存器中解码。每个子块被分为大小为T‘的K个字符号。

T=T’*N

  一个对象的每个源块的K值不一定相同，一个源块的每个子块的T’值也不一定相同。一个对象的所有源块的符号大小T是相同的，而源块的每个子块的符号数K也是相同的。

  源块和子块的构建是根据五个输入参数F（对象的传输长度）、Al（符号对齐参数）、T（源符号大小）、Z（源块数量）和N（每个源块中的子块数量），以及函数Partition[]来确定。   Partition[]输入整数对（J，I），输出整数(IL, IS, JL, JS)。目的是将将一个大小为I的块分割成J个近似相等的块，即长度为IL的JL个块和长度为IS的JS个块。

举个例子，（J，I）=（6，100），那么IL= 17，IS=16，JL=4，JS=2，此时 I L ∗ J L + I S ∗ J S = I IL*JL+IS*JS=I IL∗JL+IS∗JS=I， J S + J L = J JS+JL=J JS+JL=J

  而源对象划分为源块和子块时：

Kt = ceil(F/T)表示源对象被划分为多少个符号。

(KL, KS, ZL, ZS) = Partition[Kt, Z]表示将Kt个符号划分为Z个源块。即对象被划分为Z = ZL + ZS连续的源块，第一个ZL源块的长度为KL×T字节，其余ZS源块的长度为KS×T字节。

  如果Kt×T>F，那么出于编码的目的，最后一个符号必须在最后填充Kt×T-F的零字节。

(TL, TS, NL, NS) = Partition[T/Al, N]表示将源符号按照AI对齐后的数量，划分成N=NL+NS的连续子块，前NL子块每个由K个大小为TL×Al的连续子符号组成，其余NS子块每个由K个大小为TS×Al的连续子符号组成。

  这里说明源块和子符号块都是按照符号分的，不是将源块划分成子块，而是将符号划分成子符号块，确定T/AI=NL×TL+NS×TS。

  一个源块的第m个符号是由N个子块中每个子块的第m个子符号连接而成的。 请注意，这意味着当N>1时，一个符号不是对象的连续部分。

  每个包包含以下信息：

  每个源块独立于其他源块进行编码。 每个编码包要么完全由源符号组成（源包），要么完全由修复符号组成（修复包）。

  一个数据包可以包含来自同一源块的任何数量的符号。 如果一个源数据包中的最后一个源符号包含填充字节，填充字节不需要包括在数据包中。 否则，必须包括整个符号。

  修复包中的符号ID，X是第一个修复符号的编码符号ID，随后X+1到X+G-1，其中G为数据包中的符号数量。接受包无需知道修复数据包的总数。   与每个符号相关的是一个整数的triple（d，a，b）。在5.4.4.4中定义了一个triple generator，用于计算一个修复包中的符号相关triple： (d[0], a[0], b[0]),…, (d[G-1], a[G-1], b[G-1]) 。发送端根据修复符号triple，利用中间符号C和LT编码器LTEnc[K, C, (d[i], a[i], b[i])]，计算出要放在修复包中的ESI X的修复符号数量G。

For each i = 0, …, G-1, (d[i], a[i], b[i]) = Trip[K,X+i]

编码的目的是从K个源符号组成的源块中生成修复符号。按照个人理解，编码过程全部包含在Enc函数的符号操作中，LDPC等生成矩阵不用于生成符号，而是用于解码符号。

  符号是编码和解码过程中的基本数据单位。对于每个源块（子块），所有的符号（子符号）都是相同大小的。编码和解码时对符号（子符号）进行的按位异或操作。

K个源符号：C’[0],…, C’[K-1]→L个中间符号：C[0],…, C[L-1] 编码STEP1：由K个源符号生成L(>K)的中间符号。预编码关系在L个中间符号中保持。由5.4.2描述。 编码STEP2：由L个中间符号生成LT码（符号数量不定）。由5.4.3描述。 STEP中用到的发生器均在5.4.4中描述。

预编码步骤得到的中间符号由两组约束条件唯一确定：

  为了方便算法对源符号进行有效解码。K个源符号中的每一个都与一个Triple（d[i], a[i], b[i]）相关联。源符号triple使用triple发生器确定。即C’[i] = LTEnc[K, (C[0],…, C[L-1]), (d[i], a[i], b[i])], for all i, 0 = K + S的最小正整数。H’ = ceil(H/2)L = K+S+HC[K],…,C[K+S-1]表示S个LDPC符号，初始化为零C[K+S],…,C[L-1]表示H个Half符号，初始化为零

生成过程：

C[K],…,C[K+S-1]的值为以下过程结束时的值

For i = 0,…,K-1 do a = 1 + (floor(i/S) % (S-1)) b = i % S C[K + b] = C[K + b] ^ C[i] b = (b + a) % S C[K + b] = C[K + b] ^ C[i] b = (b + a) % S C[K + b] = C[K + b] ^ C[i]

  先定义格雷序列g[i] = i ^ (floor(i/2)) for all positive integers i，保证其中每个元素与前一个元素在对应单bit位上不同。m[k]表示g[·]的子序列，其元素的二进制表示中正好有k个非零位。m[j,k]表示序列m[k]的第j个元素，其中j=0，1，2，…。 C[K+S],…,C[L-1]的值经过以下过程生成：

For h = 0,…,H-1 do   For j = 0,…,K+S-1 do     If bit h of m[j,H’] is equal to 1 then C[h+K+S] = C[h+K+S] ^ C[j].

解码器中，中间符号C[0]、C[1]、…、C[L-1]计算举例：

G_LDPC是S×K的生成矩阵，有

Transpose[(C[0],…, C[K-1])]=G_LDPC * Transpose[(C[K], …, C[K+S-1])]

G_Half是H x (K+S)的生成矩阵

Transpose[(C[K+S], …, C[K+S+H-1])]=G_Half* Transpose[(C[0], …, C[S+K-1])]

G_LT是由LT编码器生成的编码符号的KxL生成器矩阵

Transpose[(C’[0],C’[1],…,C’[K-1])]=G_LT * Transpose[(C[0], …, C[L-1])]

显然中间符号数量 L=K+S+H 中间符号的计算可以表示为：C = (A^^-1)*D

源符号triple的生成使得对于任何K矩阵，A满秩，因此可逆。 这个计算可以通过对K个源符号C’[0], C’[1], …, C’[K-1]应用Raptor解码过程来实现，产生L个中间符号C[0], C[1], …, C[L-1] 。

  对L个中间符号C[0]、C[1]、…、C[L-1]，使用LTEcn来生成具有ESI的修复符号。

函数LTEnc[K, (C[0], C[1],…, C[L-1]), (d, a, b)]：

输入： K：源块（子块）的源符号（或子符号）的数量。注意L从K中导出，而L’在Trip()中定义为大于或等于L的最小质整数。 (C[0], C[1],…, C[L-1])：L个中间符号（子符号） (d, a, b)：d表示编码符号的度，a为[1,L’-1]之间的整数，b为[0,L’-1]之间的整数.

算法： While (b >= L) do b = (b + a) % L’ Let result = C[b]. For j = 1,…,min(d-1,L-1) do   b = (b + a) % L’   While (b >= L) do b = (b + a) % L’   result = result ^ C[b] Return result

Random Generator： 给定X，i产生一个0~m-1之间的整数。 Rand ⁡ [ X , i ,   m ] = ( V 0 [ ( X + i ) % 256 ] ∧ V 1 [ ( f l o o r ( X / 256 ) + i ) % 256 ] ) % m \operatorname{Rand}[\mathrm{X}, i, \mathrm{~m}]=(\mathrm{V} 0[(\mathrm{X}+\mathrm{i}) \% 256] \wedge \mathrm{V} 1[(\mathrm{floor}(\mathrm{X} / 256)+i) \% 256]) \% m Rand[X,i, m]=(V0[(X+i)%256]∧V1[(floor(X/256)+i)%256])%m

其中V0V1为256个元素的数组，每个元素是一个4Byte的无符号整数（见5.6）。

Degree Generator: Deg[v]，给定一个 0 ≤ v < 2 20 = 1048576 0 \leq v < 2^{20}=1048576 0≤v